package com.example.algorithm.backtracing;

import java.util.*;

/**
 * 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
 *  二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
 *
 * 示例 1：
 * 输入：graph = [[1,2],[3],[3],[]]
 * 输出：[[0,1,3],[0,2,3]]
 * 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
 *
 * 示例 2：
 * 输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
 * 输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
 *
 * 示例 3：
 * 输入：graph = [[1],[]]
 * 输出：[[0,1]]
 *
 * 示例 4：
 * 输入：graph = [[1,2,3],[2],[3],[]]
 * 输出：[[0,1,2,3],[0,2,3],[0,3]]
 *
 * 示例 5：
 * 输入：graph = [[1,3],[2],[3],[]]
 * 输出：[[0,1,2,3],[0,3]]
 */
public class Leetcode797_AllPathSourceTarget {
    public static void main(String[] args) {
        int[][] graph = {{1, 2}, {3}, {3}, {}};
        graph = new int[][] {{4, 3, 1}, {3, 2, 4}, {3}, {4}, {}};
        List<List<Integer>> res = new Solution().allPathsSourceTarget(graph);
        res.forEach(e -> System.out.println(Arrays.toString(e.toArray())));
    }

    static class Solution {
        /**
         * 回溯法:dfs遍历所有路径，当某条路径到头都不是target节点则回溯
         * @param graph
         * @return
         */
        public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
            List<List<Integer>> res = new ArrayList<>();

            boolean[] visited = new boolean[graph.length];
            dfs(graph, visited, res, new ArrayDeque<>(), 0,  graph.length - 1);

            return res;
        }

        private void dfs(int[][] graph, boolean[] visited, List<List<Integer>> res, Deque<Integer> singleRes,
                         int start, int target) {
            if (start == target) {
                singleRes.addLast(start);
                res.add(new ArrayList<>(singleRes));
                return;
            }

            if (!visited[start]) {
                visited[start] = true;
                singleRes.addLast(start);
            }

            int[] neighbors = graph[start];
            int neighborSize = neighbors.length;
            for (int i = 0; i < neighborSize ; i++) {
                int neighbor = neighbors[i];
                dfs(graph, visited, res, singleRes, neighbor, target);
                // 回溯状态
                if (singleRes.size() > 0) singleRes.removeLast();
                visited[start] = false;
            }
        }
    }
}
